package 回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 组合总和39.java
 * @createTime 2022年10月27日 17:56:00
 */
public class 组合总和39 {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> tempList = new LinkedList<>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		backTrace(candidates, target, 0, 0);
		return result;
	}

	public void backTrace(int[] candidates, int target, int curSum, int curIndex) {
		//  结束条件：当前的结果=目标值
		if (curSum == target) {
			result.add(new ArrayList<>(tempList));
			return;
		}
		// 如果当前结果>目标值，直接退出
		if (curSum > target) {
			return;
		}

		//循环遍历：因为可以重复选取，所以可以从头开始选，所以下一层的回溯开始位置还是当前位置开始
		for (int i = curIndex; i < candidates.length; i++) {
			curSum += candidates[i];
			tempList.add(candidates[i]);
			backTrace(candidates, target, curSum, i);
			tempList.removeLast();
			curSum -= candidates[i];
		}
	}
}
